In [369]:
%matplotlib inline
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
import numpy as np
import time
In [370]:
def countingSort(arr, exp1, b=2):
n = len(arr)
# The output array elements that will have sorted arr
output = [0] * (n)
# initialize count array as 0
count = [0] * (b)
# Store count of occurrences in count[]
for i in range(0, n):
index = (arr[i]/exp1)
count[ int((index)%b) ] += 1
# Change count[i] so that count[i] now contains actual
# position of this digit in output array
for i in range(1,b):
count[i] += count[i-1]
# Build the output array
i = n-1
while i>=0:
index = (arr[i]/exp1)
output[ count[ int((index)%b) ] - 1] = arr[i]
count[ int((index)%b) ] -= 1
i -= 1
# Copying the output array to arr[],
# so that arr now contains sorted numbers
i = 0
for i in range(0,len(arr)):
arr[i] = output[i]
In [371]:
# Method to do Radix Sort
def radixSort(arr, b=2):
# Find the maximum number to know number of digits
max1 = max(arr)
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed. exp is 10^i
# where i is current digit number
exp = 1
while max1/exp > 0:
countingSort(arr,exp, b)
exp *= b
In [282]:
def timeIt(N, exp=False, var_b=False):
timeList = list()
for n in N:
if exp:
arr = [np.random.randint(0, 2**n) for _ in range(n)]
arr.append(2**n)
else:
arr = [np.random.randint(0, n) for _ in range(n)]
arr.append(n)
start = time.time()
if
radixsort(arr)
end = time.time()
dt = end - start
timeList.append(dt)
return timeList
In [365]:
In [ ]:
If a list $L$ contains values in the range $1,2,3,\ldots,b^{d}$ the runtime of radix sort is $O(d(n+b))$. Assume that $d=log_{b}(n)$, and that b is an constant, say 10, then $O(n * log_{b}(n))$. Unfortunately this is the same timecomplexity as in the other comparision-sort methods. However, if it's possible to set $b=n$ (more memory has to be allocated to the sub-routine counting sort), then $O(n)$.¶
In [372]:
N =list(np.arange(2,1000))
In [ ]:
In [375]:
TIME =list()
for _ in range(10):
TIME.append(tzzzzimeIt(N))
In [368]:
VALS
Out[368]:
In [355]:
len(A[0])
In [376]:
plt.plot(N, np.mean(TIME,0))
In [283]:
N
Out[283]:
In [291]:
TIME =list()
for _ in range(500):
TIME.append(timeIt(N,2))
In [292]:
plt.plot(N, np.mean(TIME,0))
Out[292]:
In [334]:
TIME[0]
Out[334]: